This invention relates generally to branch prediction, and more particularly to a method, system and computer product for purging pattern history tables as a function of global accuracy in a state machine-based filter gshare branch predictor.
In designing a hardware mechanism in a microprocessor, the goal is to achieve high branch prediction accuracy while minimizing use of chip area and power consumption in a high frequency design. In computer architecture, a branch predictor is the part of a processor that determines whether a conditional branch in the instruction flow of a program is likely to be taken or not. Branch predictors allow processors to fetch and execute instructions without waiting for a branch to be resolved. One type of branch predictor is the bimodal predictor that has a table of two-bit entries, indexed with the least significant bits of the instruction addresses. The bimodal predictor (2-bit saturating counter) provides high accuracy on most branches, particularly those that are dominant. Dominant branches are those that often exhibit the same direction: taken vs. not-taken. The bimodal predictor often mis-predicts non-dominant branches.
Pattern-based prediction algorithms provide high accuracy on non-dominant branches but are costly in terms of area and power consumption. An effective pattern-based algorithm based on global branch history is gshare. Hybrid predictors allow for the dynamic selection among different predictors. For example, a hybrid predictor can include both a bimodal predictor and a pattern-based predictor such as gshare. A traditional hybrid predictor selects between predictors based on a per-branch indication of which predictor is best.
Global hybrid branch predictors are effective because consecutive branches often benefit from using the same predictor in a hybrid configuration. A global selection counter can be used instead of a per-branch selection table to achieve improved performance over not having one, with less overhead than a traditional hybrid scheme. One global selection counter takes up much less area than a table of them. Each predictor still needs to be big enough to support all branches being tracked. Peak performance with a global selection counter is not as good as that of a traditional hybrid but performance per area is significantly better.
Another approach, state machine based filtering, uses a pattern-based predictor such as gshare only on non-dominant branches, which allows gshare to be implemented with a much smaller pattern history table (PHT) that would otherwise be possible. The prediction state associated with each branch is updated according to a state machine that attempts to recognize those branches which would benefit from the PHT.
However, unlike traditional hybrid approaches, once the decision is made to use the gshare method on a particular branch it continues to be used even if the prediction accuracy of this method is low. Accuracy may be low due to little correlation between global history and branch outcome. Accuracy can drop due to changes in code behavior over time and also due to multiple branches conflicting with one another by using the same PHT entries. It would be desirable to have a mechanism to transition out of the PHT state.